package com.nine.algorithm.leetcode.array;

import java.util.Arrays;

/**
 * @author nine
 * @version 1.0
 * @description 合并两个有序数组（Leetcode 88 题改）
 * @date 24/5/8 22:29
 */
public class Leetcode088_2 {

	/*
	 * 将数组内两个区间内的有序元素合并
	 * [1, 5, 6, 2, 4, 10, 11]
	 * 可以视作两个有序区间
	 * [1, 5, 6] 和 [2, 4, 10, 11]
	 * 合并之后，结果仍然存于原数组中
	 * [1, 2, 4, 5, 6, 10, 11]
	 *
	 */

	public static void main(String[] args) {
		int[] a1 = {1, 5, 6, 2, 4, 10, 11};
		int[] a2 = new int[a1.length];
		// merge(a1, 0, 2, 3, 6, a2, 0);
		merge2(a1, 0, 2, 3, 6, a2);
		System.out.println("a2 = " + Arrays.toString(a2));
		System.arraycopy(a2, 0, a1, 0, a2.length);
		System.out.println("a1 = " + Arrays.toString(a1));
	}

	/*
	 * 方法一：递归实现
	 *
	 * merge([1,5,6] [2,4,10,11], a2=[]){
	 *     merge([5,6] [2,4,10,11], a2=[1]){
	 *         merge([5,6] [4,10,11], a2=[1,2]){
	 *             merge([5,6] [10,11], a2=[1,2,4]){
	 *                 merge([6] [10,11], a2=[1,2,4,5]){
	 *                     merge([] [10,11], a2=[1,2,4,5,6]){
	 *                         merge([] [], a2=[1,2,4,5,6,10,11]){
	 *                         }
	 *                     }
	 *                 }
	 *             }
	 *         }
	 *     }
	 * }
	 *
	 * @param a1   原始数组
	 * @param i    第一个有序区间的起点
	 * @param iEnd 第一个有序区间的终点
	 * @param j    第二个有序区间的起点
	 * @param jEnd 第二个有序区间的终点
	 * @param a2   结果数组
	 * @param k    a2数组的索引
	 */
	public static void merge(int[] a1, int i, int iEnd, int j, int jEnd, int[] a2, int k) {

		// 递归需要考虑结束条件
		if (i > iEnd) {
			// 第一个有序区间结束，将第二个有序区间的元素全部复制到结果数组中
			System.arraycopy(a1, j, a2, k, jEnd - j + 1);
			return;
		}

		if (j > jEnd) {
			System.arraycopy(a1, i, a2, k, iEnd - i + 1);
			return;
		}


		if (a1[i] < a1[j]) {
			a2[k] = a1[i];
			merge(a1, i + 1, iEnd, j, jEnd, a2, k + 1);
		}
		else {
			a2[k] = a1[j];
			merge(a1, i, iEnd, j + 1, jEnd, a2, k + 1);
		}

	}


	/**
	 * 方法二：双指针
	 *
	 * @param a1
	 * @param i
	 * @param iEnd
	 * @param j
	 * @param jEnd
	 * @param a2
	 */
	public static void merge2(int[] a1, int i, int iEnd, int j, int jEnd, int[] a2) {
		int k = 0;
		while (i <= iEnd && j <= jEnd) {
			if (a1[i] < a1[j]) {
				a2[k] = a1[i];
				i++;
			}
			else {
				a2[k] = a1[j];
				j++;
			}
			k++;
		}

		// 未比较的值，赋值到a2数组
		if (i > iEnd) {
			System.arraycopy(a1, j, a2, k, jEnd - j + 1);
		}
		if (j > jEnd) {
			System.arraycopy(a1, i, a2, k, iEnd - i + 1);
		}
	}

}
